<?php
// 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($value) {
        $this->val = $value;
    }
}

class Solution {
    public function hasPathSum($root, $sum) {
        if ($root == null) {
            return false;
        }
        if ($root->left == null && $root->right == null) {
            return $root->val == $sum;
        }
        return
            $this->hasPathSum($root->left , $sum - $root->val)
            ||
            $this->hasPathSum($root->right, $sum - $root->val);
    }

    public function hasPathSumOfBfs($root, $sum) {
        if ($root == null) {
            return false;
        }
        // 保存节点以及节点经过的路径和
        $queue = array();
        array_push($queue, array($root, $root->val));
        while ( !empty($queue)) {
            // 每一层的节点数
            $len = count($queue);
            // 遍历queue
            for ($index=1; $index<=$len; $index++) {
                list($path_node, $path_sum) = $queue[$index-1];
                if ($path_sum == $sum && $path_node->left == null && $path_node->right == null) {
                    return true;
                }
                // 这里已经遍历的必须unset 否则影响长度计算
                unset($queue[$index-1]);
                if ($path_node->left) {
                    array_push($queue, array($path_node->left, $path_sum + $path_node->left->val));
                }
                if ($path_node->right) {
                    array_push($queue, array($path_node->right, $path_sum + $path_node->right->val));
                }
            }
            $queue = array_values($queue);
        }
        return false;
    }
}
$TreeNode = new TreeNode(1);
(new Solution())->hasPathSumOfBfs($TreeNode, 1);